package zuo.baseUP2_Sorted_UnionField;

/**
 * @Author: Forx
 * @Data: 2021/6/17
 * @Desc: Algorithm - zuo.baseUP2_Sorted_UnionField
 * @Version: v1.0
 */
public class KMP {
    public static int[] getNext(char[] data) {
        if(data.length==1){
            return new int[]{-1};
        }
        int[] next = new int[data.length];
        next[0] = -1;
        next[1] = 0;
        int i =2;
        int cnt = 0;
        while (i < next.length){
            if(data[i-1] == data[cnt]){
                next[i++] = ++cnt;
            }else if(cnt > 0){//如果不等就往前跳
                cnt = next[cnt];
            }else {
                next[i++] = 0;
            }

        }


        return null;
    }
    public static int getIndexOf(char[] str1,char[] str2){
        if(str1==null || str2==null || str1.length<1 || str2.length < 1)return -1;
        int[] next = getNext(str2);
        int index1 = 0;
        int index2 = 0;
        //通过while的条件可以看出时间复杂度是O(N)
        while (index1 < str1.length && index2 < str2.length){
            if(str1[index1] == str2[index2]){
                index1++;
                index2++;
            }else if(index2==0){
                index1++;
            }else {
                index2 = next[index2];
            }
        }
        return index2==str2.length?index1-index2:-1;
    }



}
